\documentclass{article}

\usepackage[paper=a4paper,vmargin=0.5in]{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{hyperref}
\hypersetup{colorlinks}


\begin{document}

\title{SICP 1.13 Solution}
\author{Xueqiao Xu}
\date{\url{https://github.com/qiao/sicp-solutions}}
\maketitle

\section*{Problem:}

    \[
        Fib(n) = \left\{ 
                 \begin {array}{ll}
                 0 & \textrm{if $n = 0$} \\
                 1 & \textrm{if $n = 1$} \\
                 Fib(n - 1) + Fib(n - 2) & \textrm{otherwise}
                 \end{array}
                 \right.
    \]
    Prove that $Fib(n)$ is the closest integer to $\phi^{n} / \sqrt{5}$, where 
    $\phi = (1 + \sqrt{5}) / 2$.

\section*{Proof:}


    First, use induction to prove that 
    \begin{eqnarray}
        Fib(n) = \frac{\phi^{n} - \psi^{n}}{\sqrt{5}} \quad
        \textrm{where $\psi = \frac{1 - \sqrt{5}}{2}$}
    \end{eqnarray}


    \noindent
    For $n < 2$, we have:
    \begin{eqnarray}
        Fib(0) = 0 = \frac{\phi^{0} - \psi^{0}}{\sqrt{5}}\\
        Fib(1) = 1 = \frac{\phi^{1} - \psi^{1}}{\sqrt{5}}
    \end{eqnarray}


    \noindent
    Assume that (1) is true for $k$ and $k + 1$, where $k \in \mathrm{N}, k \geq 2$. 


    \noindent
    Then, for $n = k + 2$, we have:
    \begin{eqnarray}
        Fib(k + 2) &=& Fib(k) + Fib(k + 1) \nonumber \\
                   &=& \frac{\phi^{k} - \psi^{k}}{\sqrt{5}} + 
                       \frac{\phi^{k + 1} - \psi^{k + 1}}{\sqrt{5}} \nonumber \\
                   &=& \frac{\phi^{k}(\phi + 1) - \psi^{k}(\psi + 1)}{\sqrt{5}}
    \end{eqnarray}


    \noindent
    Note that $\phi$ and $\psi$ satify the following equations:
    \begin{eqnarray}
        \phi^{2} = \phi + 1 \\
        \psi^{2} = \psi + 1 
    \end{eqnarray}


    \noindent
    According to (5) and (6), equation (4) can be further reduced into:
    \begin{eqnarray}
        Fib(k + 2) &=& \frac{\phi^{k}(\phi^{2}) 
                       - \psi^{k}(\psi^{2})}{\sqrt{5}} \nonumber \\
                   &=& \frac{\phi^{k + 2} - \psi^{k + 2}}{\sqrt{5}} \nonumber \\
    \end{eqnarray}

    \noindent
    Therefore, (1) is true for every $k \in \mathrm{N}$\\

    \noindent
    Next, we need to prove:
    \begin{eqnarray}
        |\frac{\psi^{n}}{\sqrt{5}}| < \frac{1}{2} \qquad(\forall n \in \mathrm{N^{*}})
    \end{eqnarray}
    

    \noindent
    Note that
    \begin{eqnarray}
        \frac{\sqrt{5} - 1}{2} < \frac{1}{2} \\
        |\psi^{n + 1}| = |\psi^{n}|\cdot \frac{\sqrt{5} - 1}{2}
    \end{eqnarray}

    \noindent
    Therefore, 
    \begin{eqnarray}
        |\psi^{n + 1}| < |\psi^{n}| \qquad(\forall n \in \mathrm{N^{*}})
    \end{eqnarray}


    \noindent
    Then, since
    \begin{eqnarray}
        \frac{|\psi^{0}|}{\sqrt{5}} < \frac{1}{2}
    \end{eqnarray}


    \noindent
    It leads to the fact that (8) is true.\\

    \noindent
    Combining (1) and (12), we have:
    \begin{eqnarray}
        |\frac{\phi^{n}}{\sqrt{5}} - Fib(n)| = \frac{\psi^{n}}{\sqrt{5}} 
        < \frac{1}{2}
    \end{eqnarray}

    \noindent
    Therefore, $Fib(n)$ is the closest integer to $\phi^{n} / \sqrt{5}$.\\

    \noindent
    Q.E.D.

        
\end{document}
